GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Partitionsproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Partitionsproblem</h1>

</header>

</div>

Das Partitionsproblem (auch Zahlenaufteilungsproblem, oft mit PARTITION notiert) ist ein <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungs-</a> bzw. <a href="Entscheidbar" class="mw-redirect" title="Entscheidbar">Entscheidungsproblem</a> der <a href="Kombinatorik" title="Kombinatorik">Kombinatorik</a>.

<div class="mw-heading mw-heading2"><h2 id="Formulierung_des_Partitionsproblems">Formulierung des Partitionsproblems</h2></div>

Die Aufgabenstellung beim Partitionsproblem lautet: Gegeben sei eine (<a href="Multimenge" title="Multimenge">Multi-</a>)<a href="Menge_(Mathematik)" title="Menge (Mathematik)">Menge</a> von <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahlen</a>. Gesucht wird eine Aufteilung dieser Zahlen auf zwei Haufen, so dass die Differenz der Summen der Zahlen in den beiden Haufen möglichst klein ist.

Eine äquivalente Formulierung lautet präziser: Gegeben sei eine (Multi-)Menge A von N natürlichen Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy">. Gesucht wird eine Untermenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{1}\subset A}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{1}\subset A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6bd44df39c2037a2637990c5b255b0a59b33ea7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.639ex; height:2.509ex;" alt="{\displaystyle A_{1}\subset A}" loading="lazy">, so dass

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E:=\left|\sum _{a_{i}\in A_{1}}a_{i}-\sum _{a_{i}\in A\setminus A_{1}}a_{i}\right|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/350959dde2ae8cfcd010c2851140e6147ec1729a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:25.852ex; height:8.176ex;" alt="{\displaystyle E:=\left|\sum _{a_{i}\in A_{1}}a_{i}-\sum _{a_{i}\in A\setminus A_{1}}a_{i}\right|}" loading="lazy">

minimal wird. Eine Aufteilung, für die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26b9ec424bcc94d232be40bb53ebac3b8d5e9059.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.037ex; height:2.176ex;" alt="{\displaystyle E=0}" loading="lazy"> ist, heißt perfekte Aufteilung.

Als zusätzliche Bedingung kann man die <a href="L%C3%B6sungsmenge" title="Lösungsmenge">Lösungsmenge</a> des Partitionsproblems von vornherein einschränken, indem man nur ausgewogene Aufteilungen zulässt, in denen beide Haufen gleich groß sind, das heißt, die Anzahl der Zahlen in den Untermengen muss für gerades N gleich sein und muss sich für ungerades N um 1 unterscheiden. Auch in diesem Fall ist das Partitionsproblem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {NP}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {NP}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87fa655c6095197732cf6223a7749d794e08697d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.062ex; width:4.04ex; height:2.509ex;" alt="{\displaystyle {\mathcal {NP}}}" loading="lazy">-vollständig.<a href="#cite_note-1">[1]</a>

Wandelt man die Fragestellung ab und fragt, „Gibt es eine perfekte Aufteilung?“, so wird das oben beschriebene <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a> zu einem <a href="Entscheidbar" class="mw-redirect" title="Entscheidbar">Entscheidungsproblem</a>. Dabei sucht man nicht mehr nach der besten Aufteilung, sondern fragt nur noch nach deren Existenz.

Das Partitionsproblem gehört zu den <a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">21 klassischen NP-vollständigen Problemen</a><a href="#cite_note-2">[2]</a>, von denen <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> <a href="1972" title="1972">1972</a> die Zugehörigkeit zur Klasse der NP-vollständigen Probleme zeigen konnte.

<div class="mw-heading mw-heading2"><h2 id="Phasenübergang_im_Partitionsproblem">Phasenübergang im Partitionsproblem</h2></div>

Man beobachtet beim Partitionsproblem zwei verschiedene sogenannte Phasen: Besteht die Menge A aus vielen kleinen Zahlen, so ist anschaulich klar, dass es viele perfekte Aufteilungen gibt, und es einfach ist, eine dieser Aufteilungen zu finden (einfache Phase). Besteht A hingegen aus wenigen großen Zahlen, so ist es unwahrscheinlich, dass überhaupt eine perfekte Aufteilung existiert, und man muss alle Möglichkeiten durchprobieren, um die beste Aufteilung zu finden (harte Phase).

Zwischen der einfachen und der harten Phase beobachtet man einen Übergang, den man in Analogie zur statistischen Physik <a href="Phasen%C3%BCbergang" title="Phasenübergang">Phasenübergang</a> nennt. An diesem Phasenübergang fällt die Wahrscheinlichkeit, eine perfekte Aufteilung zu finden, sprunghaft von 1 in der einfachen Phase auf 0 in der harten Phase. Mit wachsender Anzahl N der Zahlen wird der Übergang immer schärfer.

Die Lage des Phasenübergangs in Abhängigkeit von der Anzahl und der Größe der einzelnen Zahlen lässt sich mit Methoden der <a href="Statistische_Physik" title="Statistische Physik">statistischen Physik</a> berechnen.

Alle momentan bekannten <a href="Algorithmus" title="Algorithmus">Algorithmen</a> haben dabei eine <a href="Asymptotische_Laufzeit" class="mw-redirect" title="Asymptotische Laufzeit">„worst-case-Laufzeit“</a>, die exponentiell mit der Anzahl der Zahlen N wächst, das heißt im schlimmsten Fall benötigt er zur Lösung des Entscheidungsproblem eine Rechenzeit, die exponentiell mit N ansteigt. In vielen Fällen liegt die tatsächlich benötigte Rechenzeit jedoch deutlich darunter: In der einfachen Phase stößt der Algorithmus schnell auf eine der vielen perfekten Lösungen und kann das Entscheidungsproblem somit mit „ja, es gibt eine perfekte Lösung“ beantworten und die Suche abbrechen. Auch in der harten Phase können geeignete Algorithmen (z. B. der cBLDM-Algorithmus<a href="#cite_note-npp5-3">[3]</a>) die Suche schnell mit einer negativen Entscheidung abschließen, falls keine Lösung existiert. Die „schwierigsten“ Probleme liegen somit direkt am Phasenübergang, wo erst alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{N-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{N-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b174c0991878cda28df5f3e612fdb8198b41e5f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.954ex; height:2.676ex;" alt="{\displaystyle 2^{N-1}}" loading="lazy"> Aufteilungen durchprobiert werden müssen, bevor das Problem entschieden werden kann.

<div class="mw-heading mw-heading2"><h2 id="Lösung_durch_dynamische_Programmierung">Lösung durch dynamische Programmierung</h2></div>

Mithilfe der <a href="Dynamische_Programmierung" title="Dynamische Programmierung">dynamischen Programmierung</a> kann man das Partitionsproblem in <a href="Pseudopolynomiell" title="Pseudopolynomiell">pseudopolynomieller Zeit</a> entscheiden.<a href="#cite_note-4">[4]</a>

Hierbei werden systematisch kleinere Teilprobleme betrachtet und ihre Lösungen tabelliert und rekursiv zusammengefügt.

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> die Summe der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> gegebenen Zahlen. Falls sie ungerade ist, existiert offensichtlich keine perfekte Aufteilung.

Andernfalls wird für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq i\leq N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1fae965464382285402d1bbbba16ec734acd70b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.225ex; height:2.343ex;" alt="{\displaystyle 0\leq i\leq N}" loading="lazy"> und alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq j\leq S/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq j\leq S/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/820b200d895260f46d59fcc7e74d976b3bf56ca7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.142ex; height:2.843ex;" alt="{\displaystyle 0\leq j\leq S/2}" loading="lazy"> geprüft, ob es eine Auswahl von Zahlen in der Familie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},a_{2},...,a_{i}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a_{1},a_{2},...,a_{i}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8fc81e59fadcaf6a8666681a494a1ffa3af48743.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.126ex; height:2.843ex;" alt="{\displaystyle \{a_{1},a_{2},...,a_{i}\}}" loading="lazy"> der ersten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> Zahlen gibt, deren Summe genau <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> ergibt. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31a682d568ee6a5fe51d76423186057f625ada5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i=0}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7e5f8958633770137bfba85b278e37fd8eb9092.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:5.246ex; height:2.509ex;" alt="{\displaystyle j=0}" loading="lazy"> ist dies offenbar der Fall, genauso für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fb857369fbc28dab4b5d76bb835e6f196b1d1cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i=1}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=a_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6f51c9cffdb9f7df37b314b2907f9350b816d35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:6.367ex; height:2.509ex;" alt="{\displaystyle j=a_{1}}" loading="lazy">. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i>1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dea233301b9ca8fe5dde94824f918c0ceaf7fd5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;" alt="{\displaystyle i>1}" loading="lazy"> und alle anderen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> dagegen nicht. Dies ist der Anfang der Rekursion, der in der ersten Zeile einer Tabelle notiert wird. Für die weiteren Zeilen ergeben sich die Einträge nach folgender Rekursion: Eine Auswahl für

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ef21910f980c6fca2b15bee102a7a0d861ed712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.604ex; height:2.843ex;" alt="{\displaystyle (i,j)}" loading="lazy"> existiert genau dann, wenn entweder bereits eine für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i-1,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i-1,j)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1a4d11f6f8e476a0335bad7ce61434bc49cbc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.607ex; height:2.843ex;" alt="{\displaystyle (i-1,j)}" loading="lazy"> existiert, oder wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j>a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j>a_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e96385ceb6d19f032a8d75eb740ec45e7acb3159.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:6.113ex; height:2.509ex;" alt="{\displaystyle j>a_{i}}" loading="lazy"> ist und eine Auswahl für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i-1,j-a_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i-1,j-a_{i})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/851f1bffa864b9a85216357f8631ff981b443a55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.476ex; height:2.843ex;" alt="{\displaystyle (i-1,j-a_{i})}" loading="lazy"> existiert.

Die Antwort auf das Entscheidungsproblem gibt der letzte Eintrag in der Tabelle (für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdac8e08be2f4b48e5a4f629215de7d8c404fbde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.965ex; height:2.176ex;" alt="{\displaystyle i=N}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=S/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=S/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4bdc21258e74c1da67bd730e5b097cafdc8b8d92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:7.907ex; height:2.843ex;" alt="{\displaystyle j=S/2}" loading="lazy">) an.

Die <a href="Komplexit%C3%A4t_(Informatik)" title="Komplexität (Informatik)">Komplexität</a> dieses <a href="Algorithmus" title="Algorithmus">Algorithmus</a> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(N\cdot S)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(N\cdot S)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6275d41a8c665bbc4f3b066bcb38ac6ae1434c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.901ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(N\cdot S)}" loading="lazy">.

Das folgende Beispiel zeigt eine Implementierung des Algorithmus in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C%2B%2B" title="C++">C++</a>.<a href="#cite_note-5">[5]</a><div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre>#include <iostream>

using namespace std;

// Diese Funktion prüft, ob es eine Aufteilung der Menge mit gleichen Summen gibt und gibt dann true zurück, sonst false

bool findPartition(int numbers[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++) // for-Schleife, die die Summe der Zahlen berechnet

{

sum += numbers[i];

}

if (sum % 2 != 0) // Wenn die Summe ungerade ist, wird false zurückgegeben

{

return false;

}

bool* part = new bool[sum / 2 + 1]; // Deklariert ein Array, in dem gespeichert wird, ob die Zahlen 0, 1, 2, ... als Summe einer Teilmenge der gegebenen Zahlen dargestellt werden können

for (int i = 0; i <= sum / 2; i++) // for-Schleife, die das Array initialisiert

{

part[i] = false;

}

{

for (int j = sum / 2; j >= numbers[i]; j--) // In dieser for-Schleife wird geprüft, ob Halbe Gesamtsumme - Zahl mit Index i als Summe einer Teilmenge von Zahlen mit Index kleiner als i dargestellt werden kann

{

if (part[j - numbers[i]] || j == numbers[i]) // Wenn die Summe j - Zahl mit Index i dargestellt werden kann oder die Zahl mit Index i gleich j ist, wird das Element für die Summe j auf true gesetzt

{

part[j] = true;

}

return part[sum / 2]; // Gibt das Element für die halbe Gesamtsumme der Zahlen zurück. Dieses Element vom Typ bool gibt an, ob diese Summe dargestellt werden kann.

}

// Hauptfunktion die das Programm ausführt

int main()

{

int numbers[] = { 1, 3, 3, 2, 3, 2 };

int n = sizeof(numbers) / sizeof(numbers[0]); // Variable für die Anzahl der Zahlen

if (findPartition(numbers, n)) // Wenn eine Aufteilung mit gleichen Summen gefunden wurde

{

cout << "Es gibt eine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole

}

else

{

cout << "Es gibt keine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Steven S. Skiena: The Algorithm Design Manual. Corrected 2nd printing. Springer u. a., New York NY u. a. 1998, ISBN 0-387-94860-0.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Michael R. Garey, <a href="David_Stifler_Johnson" title="David Stifler Johnson">David Stifler Johnson</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computers and Intractability</cite>. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 223 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Partitionsproblem&rft.au=Michael+R.+Garey%2C+David+Stifler+Johnson&rft.btitle=Computers+and+Intractability&rft.genre=book&rft.isbn=0716710455&rft.pages=223" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Michael R. Garey, <a href="David_Stifler_Johnson" title="David Stifler Johnson">David Stifler Johnson</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computers and Intractability</cite>. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 47 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Partitionsproblem&rft.au=Michael+R.+Garey%2C+David+Stifler+Johnson&rft.btitle=Computers+and+Intractability&rft.genre=book&rft.isbn=0716710455&rft.pages=47" style="display:none">

</li>

<li id="cite_note-npp5-3"><a href="#cite_ref-npp5_3-0">↑</a> S. Mertens: A complete anytime algorithm for balanced number partitioning, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/9903011">cs/9903011</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Michael R. Garey, <a href="David_Stifler_Johnson" title="David Stifler Johnson">David Stifler Johnson</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computers and Intractability</cite>. A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5, S. 90–92 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Partitionsproblem&rft.au=Michael+R.+Garey%2C+David+Stifler+Johnson&rft.btitle=Computers+and+Intractability&rft.genre=book&rft.isbn=0716710455&rft.pages=90-92" style="display:none">

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/partition-problem-dp-18/">Partition problem</a>

</li>

</ol>

/* start https://de.wikipedia.org/ */

.mw-parser-output div.klappleiste{border:1px solid var(--dewiki-rahmenfarbe1);clear:both;font-size:95%;box-sizing:border-box;margin-top:1.5em;padding:2px}.mw-parser-output div.klappleiste:after{clear:both;content:"";display:block}.mw-parser-output div.klappleiste-bild{float:left;padding:2px}.mw-parser-output div.klappleiste-kopf{background:var(--dewiki-hintergrundfarbe5);color:var(--color-base,#202122);text-align:center;font-weight:bold}.mw-parser-output div.klappleiste.mw-collapsed .klappleiste-bild{display:none}.mw-parser-output div.klappleiste+div.klappleiste,.mw-parser-output div.klappleiste+link+div.klappleiste,.mw-parser-output div.klappleiste+link+link+div.klappleiste,.mw-parser-output div.klappleiste+link+style+div.klappleiste,.mw-parser-output div.klappleiste+style+div.klappleiste,.mw-parser-output div.klappleiste+style+style+div.klappleiste,.mw-parser-output div.klappleiste+style+link+div.klappleiste{margin-top:-1px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}

/* end https://de.wikipedia.org/ */

</style>

<div class="klappleiste-kopf"><a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">Karps 21 NP-vollständige Probleme</a></div>

<a href="Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik" title="Erfüllbarkeitsproblem der Aussagenlogik">Erfüllbarkeitsproblem der Aussagenlogik</a> |

<a href="Cliquenproblem" title="Cliquenproblem">Cliquenproblem</a> |

<a href="Mengenpackungsproblem" title="Mengenpackungsproblem">Mengenpackungsproblem</a> |

<a href="Knoten%C3%BCberdeckungsproblem" class="mw-redirect" title="Knotenüberdeckungsproblem">Knotenüberdeckungsproblem</a> |

<a href="Mengen%C3%BCberdeckungsproblem" title="Mengenüberdeckungsproblem">Mengenüberdeckungsproblem</a> |

<a href="Feedback_Arc_Set" title="Feedback Arc Set">Feedback Arc Set</a> |

<a href="Feedback_Vertex_Set" title="Feedback Vertex Set">Feedback Vertex Set</a> |

<a href="Hamiltonkreisproblem" title="Hamiltonkreisproblem">Hamiltonkreisproblem</a> |

<a href="Ganzzahlige_lineare_Optimierung#0.2F1-Programmierung" title="Ganzzahlige lineare Optimierung">Integer Linear Programming</a> |

<a href="3-SAT" title="3-SAT">3-SAT</a> |

<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">graph coloring problem</a> |

Covering by cliques |

<a href="Problem_der_exakten_%C3%9Cberdeckung" title="Problem der exakten Überdeckung">Problem der exakten Überdeckung</a> |

3-dimensional matching |

<a href="Steinerbaumproblem" title="Steinerbaumproblem">Steinerbaumproblem</a> |

<a href="Hitting-Set-Problem" title="Hitting-Set-Problem">Hitting set</a> |

<a href="Rucksackproblem" title="Rucksackproblem">Rucksackproblem</a> |

Job sequencing |

<a class="mw-selflink selflink">Partitionsproblem</a> |

<a href="Maximaler_Schnitt" title="Maximaler Schnitt">Maximaler Schnitt</a>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-06" href="https://de.wikipedia.org/wiki/?title=Partitionsproblem&oldid=255787013">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>